Multi-layer network switches and routers in data communications network sometimes employ specialized application-specific integrated circuits (ASICs) designed to perform a large number of switching and routing operations on packet data. These ASICs include network processors (NPs) adapted to perform many of the Open Systems Interconnect (OSI) data link layer (Layer 2) switching operations and network layer (Layer 3) routing operations. NPs with routing capabilities generally compile and maintain routing tables that are used to retrieve the next-hop address for thousands of routes. The routing tables, e.g., Routing Forwarding Databases (RFDs), are retained in on-chip registers that are both fast and programmable.
While the register of a NP may store thousands of network routes, this may be insufficient to accommodate all the network addresses learned by the router in the course of operation. When the number of routes exceeds the maximum capacity of the NP, an attempt to write additional routes may fail on insertion or lead to unpredictable routing behavior. As a result, contemporary routers attempt to avoid such problems by limiting the number of routes saved to the NP and deleting those routes that exceed its maximum storage capacity. This practice, however, is not a solution because it results in the deletion of valid routes even if the routes are used more frequently than routes already retained by the registers.
There is therefore a need for a system and method to augment the storage capacity of NPs in a manner that provides a NP with access to all known routes while giving precedence to the routes that are used most frequently.